iT邦幫忙

2024 iThome 鐵人賽

DAY 10
0

Problem :

Given a string s containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1 :

**Input: s = "()"
Output: true**

Example 2 :

**Input: s = "()[]{}"
Output: true**

Example 3 :

**Input: s = "(]"
Output: false**

Example 4 :

**Input: s = "([])"
Output: true**

核心思維 :

  1. 定義堆疊以儲存括號

  2. 遍歷字串中的字符

    • 若當前字符是左括號,將其放入堆疊中
    • 若滿足
      1.字符是右括號
      2.堆疊不為空
      3.堆疊頂端的左括號能夠對應右括號,則將堆疊頂端的元素移出
    • 若沒有對應的括號則回傳false
  3. 所有括號都配對完成,堆疊內應為空,否則回傳false

程式碼 :

class Solution {
public:
    bool isValid(string s) {
        //定義堆疊來儲存括號
        std::stack<int> mystack;
        //遍歷字串中的字符
        for(char c: s){
            //若當前字符是左括號,則放入堆疊中
            if(c == '(' || c == '{' || c == '['){
                mystack.push(c);
            //若滿足當前字符是右括號,堆疊不為空,並且堆疊頂端的左括號能夠對應右括號,則將堆疊頂端的元素移出
            }else if(c == ')' && !mystack.empty() && mystack.top() == '('){
                mystack.pop();
            }else if(c == '}' && !mystack.empty() && mystack.top() == '{'){
                mystack.pop();
            }else if(c == ']' && !mystack.empty() && mystack.top() == '['){
                mystack.pop();
            }else{
                //若沒有對應的括號,回傳false
                return false;
            }
        }
        //當所有括號都配對完成,堆疊內為空,否則回傳false
        return mystack.empty();
    }
};

結論 :

這題的目標是將括號放入堆疊中,並且檢查是否匹配,其中透過字符是左括號、右括號及是否有對應的括號來做判斷並進行字符的配對,其中活用堆疊操作簡單的特性,透過設立條件的方式進行配對,可以快速辨別此字串是否符合條件,善用堆疊的特性可以達成簡單明瞭且較短的執行時間的效益。


上一篇
Day9 演算法介紹 : 堆疊(Stack)
下一篇
Day11 Stack 題目2 : 394. Decode String
系列文
C++刷題:LeetCode Top 100 Liked30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言